package org.algorithm.Sort;


public class MergeSort1 {

    public static void main(String[] args) {
        int [] arr ={1,3,2,6,5};
        int [] temp = new int[arr.length];
        split(arr,0,arr.length-1,temp);

        for (int num:arr) {
            System.out.println(num);
        }
    }


    public  static void  split(int [] arr,int left,int end,int[] tempArr){
        if (left>=end){
            return;
        }

        int mid =(left+end)>>>1;

        split(arr,left,mid,tempArr);
        split(arr,mid+1,end,tempArr);

        merge(arr,left,mid,mid+1,end,tempArr);
    }


    public static void merge(int [] arr,int leftStart,int leftEnd,int rightStart,int rightEnd,int [] tempArr){

        int currIndex = leftStart;

        int leftIndex = leftStart;

        int rightIndex = rightStart;

        while (leftIndex<=leftEnd && rightIndex<=rightEnd){
            if (arr[leftIndex]<arr[rightIndex]){
                tempArr[currIndex]=arr[leftIndex];
                leftIndex++;
            }else {
                tempArr[currIndex]=arr[rightIndex];
                rightIndex++;
            }
            currIndex++;
        }

        if (leftIndex<=leftEnd){
            for (int i = leftIndex; i <=leftEnd ; i++,currIndex++) {
                tempArr[currIndex]=arr[i];
            }
        }

        if (rightIndex<=rightEnd){
            for (int i = rightIndex; i <=rightEnd ; i++,currIndex++) {
                tempArr[currIndex]=arr[i];
            }
        }

        for (int i = leftStart;i<=rightEnd;i++){
            arr[i]=tempArr[i];
        }

    }



}
